#define _CRT_SECURE_NO_WARNINGS 1

# include<bits/stdc++.h>
using namespace std;


class Solution {
public:
    int tribonacci(int n) {
        vector<int> arr = { 0,1,1,2 };
        if (n <= 3)
        {
            return arr[n];
        }
        for (int i = 3; i <= n; ++i)
        {
            arr[3] = arr[0] + arr[1] + arr[2];
            arr[0] = arr[1];
            arr[1] = arr[2];
            arr[2] = arr[3];
        }
        return arr[3];
    }
};


class Solution {
public:
    int waysToStep(int n) {
        const int MOD = 1e9 + 7;
        vector<long long> arr = { 1,1,2,4 };
        if (n <= 3)
        {
            return arr[n];
        }
        for (int i = 3; i <= n; ++i)
        {
            arr[3] = ((arr[0] + arr[1]) % MOD + arr[2]) % MOD;
            arr[0] = arr[1];
            arr[1] = arr[2];
            arr[2] = arr[3];
        }
        return arr[3];
    }
};